Decision tree learning, used in statistics, data mining and machine learning, uses a decision tree as a predictive model which maps observations about an item to conclusions about the item's target value. More descriptive names for such tree models are classification trees or regression trees. In these tree structures, leaves represent class labels and branches represent conjunctions of features that lead to those class labels.
In machine learning, building a model or decision tree based on a large data set can take a long time. Further, the time and resources necessary to build a model increases as the required quality or depth of the model increases. Approximate histograms have been used in building decision trees. An approximate histogram was introduced by Messrs. Ben-Haim and Yom-Tov, “A Streaming Parallel Decision Tree Algorithm” (J. Machine Learning Research 11 (2010) 849-872). The histogram is built in a streaming fashion and acts as a memory-constrained approximation (or compression) of the entire dataset.
Tyree, et al. extend the histogram so that it approximates the relationship between two numeric fields. (WWW 2011-Session: Ranking, Mar. 28-Apr. 1, 2011, Hyderabad, India at 387.) Of course, a “brute force” approach of applying ever increasing resources to the problem, using known parallel and distributed processing techniques, can be useful. Still, the need remains for more effective methods to build decision trees quickly, and to better support classification problems.